//
// Created by PC on 2023/8/6.
/*
 * https://oj.youdao.com/problem/15384?from=contest
 * 有道小图灵
(编程思维赛项-C++普及组)
第三题《小图灵的新游戏》
小图灵的新游戏
题目描述
小图灵新入手了一款PS333平台的游戏，在游戏中从起点到终点共有n个得分点，编号为1-n,需要使用灵能手套才能获得得分点分数，灵能手套经过充能后只可以使用3次。
游戏最终成绩的计算规则如下：假设通过灵能手套获取了三个不同的编号分别为i,j,k的得分点的分数ai,aj,ak,最终成绩为3个得分点分数总和先减去所选取三点中编号最小值再减去所选取三点中编号最大值，即ai+aj+ak-min(i,j,k)-max(i,j,k)。
请你编写程序帮助小图灵获得最好成绩。
注：min(i,j,k)表示i,j,k中的最小值，max(i,j,k)表示i,j,k中的最大值。
输入描述
第一行包含一个整数t,表示有t组测试数据；每组测试数据包含两行：
第一行包含一个整数n,表示游戏中得分点的数量；
第二行包含n个整数，表示从起点到终点n个得分点的分数，第i个得分点的分数为ai
输出描述每组测试数据一行，输出小图灵所能够获得的最好成绩。
样例1
输入
1
6
122333
输出
1
样例2
输入
2
6
1913427711
8
87654321
输出
54
17
样例3
输入
1
10
12399910101010
输出
17
提示
对于20%的数据：1≤t≤10,3≤n≤100;
对于60%的数据：1≤t≤20,3≤n≤10³;
对于100%的数据：1≤t≤100,3≤n≤10⁵,1≤a;≤10^8。输入文件的大小不超过10MB。
时间限制：1000ms内存限制：256MB
 * */
// 通过6/10个测试用例
// 暴力穷举的改进版, 中间值在两边的值之间寻找最大值, 还是后4个测试用例超时


#include <iostream>

using namespace std;


int main()
{
    int t, n, mi = 1, ma = 3;
    cin >> t;
    while (t--)
    {
        long long ans = -1;
        cin >> n;
        long long l[n + 1] = {0};
//        int sum = 0,cur;
        for (int m = 1; m <= n; ++m)
        {
            cin >> l[m];
        }
        for (int i = 1; i <= n; ++i)
        {
//            int j = i + 1;
            long long maxmid = l[i + 1];// 索引i和k中间的最大值
            int k = i + 2;
            while (k < n)
            {
                // 往后移动一位 最大值更新一次
                maxmid = max(maxmid, l[k-1]);
                ans = max(ans, l[i] + maxmid + l[k] - i - k);
                ++k;
            }
        }
        cout << ans << endl;
    }
    return 0;
}